Technical Field
The present disclosure relates to parallel processing systems, and more specifically to reducing blocking instances in parallel processing systems performing operations on trees.
Related Art
A parallel processing system generally refers to a system in which multiple execution entities operate in parallel or concurrently in processing various data resources (or values for corresponding entities). For example, a system may contain multiple processors operating independently to provide many threads, with several threads executing concurrently on corresponding data resources.
A tree refers to hierarchical organization of data resources. A tree is characterized by a root and various other nodes in parent-child relationships (represented by a node pointer from the parent to child), with each node commonly storing a corresponding one of the data resources of interest. Each non-root node is either a direct child of the root or has a unique path to the root through other intermediate nodes. The nodes at a same distance (i.e., number of intermediate nodes) from the root are said to be at same level. The maximum level present in a tree is referred to as the height/depth of the tree.
There are several types of operations performed on trees. The tree operations can be viewed broadly as falling into two categories—traversal operations and change operations. Traversal operations are primarily read operations intended for examining the data resources stored in nodes. To access a desired data resource or to identify data resources with desired attributes, multiple nodes may be accessed, which is termed as traversal. In general, a traversal operation entails examining content of a node and determining any next nodes to access (based on the examined content), and access such determined next nodes.
Change operations on the other hand may either update the data resource stored in the node or change the structure/topology of the tree by adding/deleting nodes or even shifting the nodes. Shifting implies moving the position of a node to a different position in the tree. Shifting may be performed, for example, to obtain the desired balancing characteristic (e.g., rotation for minimal height in case of AVL (Adelson, Velskii and Landis) trees), as is well known in the relevant arts.
There are often instances of blocking, typically when a change operation is sought to be performed concurrent (in parallel) with another change or traversal operation. Blocking implies that the execution entity assigned to perform the tree operation is required to wait, though the execution entity is otherwise ready to continue with the performance of the tree operation.
For example, if a change operation is already in progress, access to at least some of the nodes of the tree may be denied to otherwise ‘ready’ execution entities (causing blocking of the ready execution entities), irrespective of whether such execution entities are performing traversal or change operations. Similarly, blocking may occur when a change operation is ready to be performed, while a traversal operation is already in progress.
Aspects of the present disclosure reduce at least some of such blocking instances, as described below with examples.
In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.